﻿using System.Runtime.InteropServices.Marshalling;

namespace LearnDSSortings;

public class QuickSort
{
    public void Sort(int[] arr, int low, int high)
    {
        if (low < high)
        {
            int pi = Partition(arr, low, high);
            Sort(arr, low, pi - 1);
            Sort(arr, pi + 1, high);
        }
    }

    private int Partition(int[] arr, int low, int high)
    {
        int pivot = arr[low];
        int i = low + 1;
        int j = high;
        do
        {
            while (i <= j && arr[i] <= pivot)
            {
                i = i + 1;
            }

            while (i <= j && arr[j] > pivot)
            {
                j = j - 1;
            }

            if (i <= j)
            {
                Swap(arr, i, j);
            }
        } while (i < j);

        Swap(arr, low, j);
        return j;
    }

    private void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}